package com.icbc.DataStructuresAndAlgorithms;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 数组转赫夫曼树
 */
public class HuffmamTreeDomo {
	public static void main(String[] args) {
		/*int[] arr = {13,7,8,3,29,6,1};
		getHuffmanTree(arr).perOrder();*/
		String data = "i like like like java do you like a java";
		Map<Character, Integer> zifu = new HashMap<>();
		for (int a = 0 ; a < data.length() ; a ++){
			char c = data.charAt(a);
			if (zifu.containsKey(c)){
				zifu.put(c,zifu.get(c) + 1 );
			}else{
				zifu.put(c,1);
			}
		}
		
	}
	
	public static Node getHuffmanTree(int[] arr){
		//这里的思路是:首先将arr数组中的元素创建成Node节点,放入list集合中
		List<Node> nodes = new ArrayList<>();
		for (int v : arr) {
			nodes.add(new Node(v));
		}
		//由于在里面会不停的对nodes进行remove操作,直到最后只剩下一个节点为止
		while (nodes.size() > 1) {
			//将集合进行排序,这里是从小到大排序
			nodes.sort((a, b) -> {
				return a.value - b.value;
			});
			//获取出权值最小的两个节点
			Node leftNode = nodes.get(0);
			Node rightNode = nodes.get(1);
			//获取出节点后,组成一个新的树
			Node parent = new Node(leftNode.value + rightNode.value);
			parent.left = leftNode;
			parent.right = rightNode;
			//将集合中上面的两个节点删掉,再将parent加入集合中
			nodes.remove(leftNode);
			nodes.remove(rightNode);
			nodes.add(parent);
		}
		//将头节点返回
		return nodes.get(0);
	}
}

class Node{
	int value;
	Node left;
	Node right;
	
	//前序遍历
	public void perOrder(){
		System.out.println(this);
		if (this.left != null){
			this.left.perOrder();
		}
		if (this.right != null){
			this.right.perOrder();
		}
	}
	
	public Node(int value) {
		this.value = value;
	}
	
	@Override
	public String toString() {
		return "Node{" +
				"value=" + value +
				'}';
	}
}
